﻿// 215. 破译密码.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*

https://www.acwing.com/problem/content/217/

达达正在破解一段密码，他需要回答很多类似的问题：

对于给定的整数 a,b 和 d，有多少正整数对 x,y，满足 x≤a，y≤b，并且 gcd(x,y)=d。

作为达达的同学，达达希望得到你的帮助。

输入格式
第一行包含一个正整数 n，表示一共有 n 组询问。

接下来 n 行，每行表示一个询问，每行三个正整数，分别为 a,b,d。

输出格式
对于每组询问，输出一个正整数，表示满足条件的整数对数。

数据范围
1≤n≤50000,
1≤d≤a,b≤50000
输入样例：
2
4 5 2
6 4 3
输出样例：
3
2
提示:gcd(x,y) 返回 x，y 的最大公约数。


37
2255 2805 55


1307

*/

#include <iostream>
#include <algorithm>
#include <cstring>


using namespace std;

typedef long long LL;
const int N = 50010;
int primes[N], cnt;
bool st[N];
long long  mobius[N], sum[N];
int n, T;
 
void init(int x) {
	mobius[1] = 1;
	for (int i = 2; i <= x; i++) {
		if (!st[i]) {
			primes[cnt++] = i;
			mobius[i] = -1;
		}
		for (int j = 0; j < cnt && i * primes[j] <= x; j++) {
			st[i * primes[j]] = true;
			if (i % primes[j] == 0) {
				mobius[i * primes[j]] = 0;
				break;
			}
			else mobius[i * primes[j]] = -mobius[i];
		}
	}

	for (int i = 1; i <= x; i++) sum[i] = sum[i - 1] + mobius[i];
}


int main()
{
	init(N - 1);
	cin >> T;
	while (T--) {
		int a, b, d; cin >> a >> b >> d;
		a /= d; b /= d;
		int n = min(a, b);
		int r = 0; long long ans = 0;
		for (int i = 1; i <= n; i = r + 1) {
			r = min(n, min(a / (a / i), b / (b / i)));
			ans += (sum[r] - sum[i - 1]) * (a / i) * (b / i);
		}

		cout << ans << endl;
	}
	 


	return 0;
}

